#include <stdio.h>
#include <stdlib.h>
#include "binTree.h"
#include "queue.h"

btNode_t *createNode(int data) {
    btNode_t *newNode = (btNode_t*) malloc(sizeof(btNode_t));
    if (newNode) {
        newNode->data = data;
        newNode->left = NULL;
        newNode->right = NULL;
    }
    return newNode;
}

void preOrder(btNode_t *tree) {
    if (tree != NULL) {
        printf("%d ", tree->data);
        preOrder(tree->left);
        preOrder(tree->right);
    }
}
void inOrder(btNode_t *tree){
        if (tree) {
        inOrder(tree->left);
        printf("%d ", tree->data);
        inOrder(tree->right);
    }
}
void postOrder(btNode_t *tree){
    if (tree) {
        postOrder(tree->left);
        postOrder(tree->right);
        printf("%d ", tree->data);
    }
}

void levelOrder(btNode_t *tree){
    queue_t queueB;

    if (tree == NULL) return; 
    if (init(&queueB, 100) == QUEUE_FAIL) {
        printf("initial queue error\n");
        return;
    }
    
    enqueue(&queueB, (void*)tree);
    while(!isEmpty(&queueB)) {
        btNode_t *node = dequeue(&queueB);
        if (node != NULL) {
            printf("%d ", node->data);
            enqueue(&queueB, (void*) node->left);
            enqueue(&queueB, (void*) (node->right));
        }
    }
    free(queueB.elements);
}

btNode_t * search(btNode_t *tree, int key) {
    btNode_t *ret;
    if (tree == NULL) 
        ret = NULL;
    else {
        if (tree->data == key) 
            ret = tree;
        else if(search(tree->left, key) != NULL)
            ret = tree->left;
        else if(search(tree->right, key) != NULL)
            ret = tree->right;
        else
            ret = NULL;
    }   
    return ret;
}

void insert(btNode_t *tree, int key) {
    queue_t queueB;
    btNode_t *parent=NULL;

    if (tree == NULL) return; 
    if (init(&queueB, 100) == QUEUE_FAIL) {
        printf("initial queue error\n");
        return;
    }
    
    enqueue(&queueB, (void*)tree);
    while(!isEmpty(&queueB)) {
        btNode_t *node = dequeue(&queueB);
        if (node != NULL) {
            //check left or right child is NULL ?
            if (node->left == NULL){
                parent = node;
                break;
            } else if(node->right==NULL) {
                parent = node;
                break; 
            } else {
                parent = NULL;
                enqueue(&queueB, (void*) node->left);
                enqueue(&queueB, (void*) (node->right));
            }
        }
    }
    free(queueB.elements);
    if (parent != NULL) {
        btNode_t *newNode = (btNode_t *)malloc(sizeof(btNode_t));
        newNode->data = key;
        newNode->left = NULL;
        newNode->right = NULL;
        if (parent->left == NULL) {
            parent->left = newNode;
        } else {
            parent->right = newNode;
        }
    }
}

static void deleteDeepest(btNode_t* tree, btNode_t* dNode) {
    queue_t queueB;
    btNode_t *currNode;
    init(&queueB, 100);
    enqueue(&queueB, tree);
    while(!isEmpty(&queueB)) {
        currNode = (btNode_t*) dequeue(&queueB);
        if (currNode==dNode) {
            free(dNode);
            break;
        }
        if (currNode->left) {
           if (currNode->left == dNode) {
                currNode->left = NULL;
                free(dNode);
                break;
           }
           enqueue(&queueB, (void *) currNode->left);
        }
        if (currNode->right) {
           if (currNode->right == dNode) {
                currNode->right = NULL;
                free(dNode);
                break;
           }
           enqueue(&queueB, (void *) currNode->right);
        }
    }

    free(queueB.elements);
}

btNode_t * delete(btNode_t *tree, int key){
    queue_t queueB;
        
    if (tree==NULL) return NULL;
    if (tree->left==NULL && tree->right==NULL) {
        if (tree->data == key) {
            free(tree);
            return NULL;
        } else 
            return tree;
    }

    init(&queueB, 100);
    btNode_t *keyNode=NULL;
    btNode_t *currNode;
    enqueue(&queueB, tree);

    while(!isEmpty(&queueB)) {
        currNode = (btNode_t *)dequeue(&queueB);
        if (currNode->data == key)
            keyNode = currNode;
        if (currNode->left != NULL) enqueue(&queueB, (void *)currNode->left);
        if (currNode->right != NULL) enqueue(&queueB, (void *)currNode->right);
    }
    //At here, currNode is deepest node of tree

    if (keyNode != NULL) {
        keyNode->data = currNode->data;
        deleteDeepest(tree, currNode);
    }
    free(queueB.elements);
}


int height(btNode_t* tree) {
    if (tree == NULL)
        return -1;

    // compute the height of left and right subtrees
    int lHeight = height(tree->left);
    int rHeight = height(tree->right);

    return (lHeight > rHeight ? lHeight : rHeight) + 1;
}
